leetcode 1020 飞地的数量

问题不复杂，就是不断的遍历，然后看有1的方块能否接触带岸边。

题目

给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。

移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。

返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1：

输入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：
有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
示例 2：

输入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：
所有 1 都在边界上或可以到达边界。

提示：

1 <= A.length <= 500
1 <= A[i].length <= 500
0 <= A[i][j] <= 1
所有行的大小都相同

思路

由题目可知，要求的是不能挨着四条边界的1的个数，不能挨着四条边界，代表没有办法通过相邻的1接触到四条边界，那从四条边界的1开始遍历，将能够通过四条边界接触到的1全部置为0，那么剩下的就全部是飞地了，这些1是没有办法接触到四条边界的。

code

 int chuli(vector<vector<int>>& A,int i ,int j,int h,int l)
{
    A[i][j]=0;//代表不是飞地，所以置0；
    if(((i-1)>=0)&&(A[i-1][j]==1))//和不是飞地的1挨着的1肯定也不是飞地。
        chuli(A,i-1,j,h,l);
    if(((i+1)<h)&&(A[i+1][j]==1))//往四个方向分别遍历，找到1就置为0；
        chuli(A,i+1,j,h,l);
    if(((j-1)>=0)&&(A[i][j-1]==1))
        chuli(A,i,j-1,h,l);
    if(((j+1)<l)&&(A[i][j+1]==1))
        chuli(A,i,j+1,h,l);
    return 0;
}
int numEnclaves(vector<vector<int>>& A) {
    int res=0;
    int h=A.size();
    int l=A[0].size();
    for(int j=0;j<l;j++)//从四条边出发，挨着四条边的1肯定不是飞地，将它们置为0；
        if(A[0][j]==1)
            chuli(A,0,j,h,l);
    for(int j=0;j<l;j++)
        if(A[h-1][j]==1)
            chuli(A,h-1,j,h,l);
    for(int i=0;i<h;i++)
        if(A[i][0]==1)
            chuli(A,i,0,h,l);
    for(int i=0;i<h;i++)
        if(A[i][l-1]==1)
            chuli(A,i,l-1,h,l);
    for(int i=0;i<h;i++)//数组中剩下的1肯定就是飞地，将它们求和相加就可以了。
    {
        for(int j=0;j<l;j++)
            res+=A[i][j];
    }
    return res;
}